/*
FROM: http://www.newsmth.net/bbscon.php?bid=335&id=322315

发信人: azulla (azulla), 信区: CPlusPlus
标  题: 也发一个N维动态数组（内存连续分配）模板
发信站: 水木社区 (Tue Apr 19 00:06:39 2011), 站内

看了fentoyal写的《[技巧]任意维的连续空间数组的动态分配方法（模板）》
http://www.newsmth.net/bbstcon.php?board=CPlusPlus&gid=321891

觉得空间浪费比较严重，访问内存开销太大。感觉boost的MultiArray不够轻量，C99的变长数组只能在栈上，就花了几个小时实现了下。

原理很简单，就是重载operator[]返回一个代理类。看了下三维时的汇编代码(g++ -O3)，临时对像都被优化掉，跟手动计算一样高效。

用法：
unsigned src[3] = { 4, 3, 2};
Marray<int, 3> mm(src);
mm[3][2][1] = 7;
const int *p = &mm;

*/

#include <stdlib.h>
#include <assert.h>
#include <iostream>

template< typename R, size_t M >
struct Proxy {
	R *ptr;
	size_t *total_size; //total_size[M] M维数组的大小, total_size[0]为边界指针的地址
	Proxy( R *p, size_t *q ) : ptr( p ), total_size( q ) {}

	R *operator & () { assert( size_t( ptr ) < total_size[0] );  return ptr; } //--
	const R *operator & () const { assert( size_t( ptr ) < total_size[0] );  return ptr; }

	Proxy< R, M - 1 > operator [] ( size_t index )
	{
		return Proxy< R, M - 1 >( ptr + total_size[M - 1] * index, total_size );
	}

	const Proxy< R, M - 1 > operator [] ( size_t index ) const
	{
		return Proxy< R, M - 1 >( ptr + total_size[M - 1] * index, total_size );
	}
};

template< typename R > struct Proxy< R, 0 >{};

template< typename R >
struct Proxy< R, 1 >{
	R *ptr;
	size_t *total_size; //total_size[M] M维数组的大小, total_size[0]为边界指针的地址
	Proxy( R *p, size_t *q ) : ptr( p ), total_size( q ) {}

	R *operator & () { assert( size_t( ptr ) < total_size[0] );  return ptr; } //--
	const R *operator & () const { assert( size_t( ptr ) < total_size[0] );  return ptr; }

	//---特化
	R & operator [] ( size_t index )
	{
		assert( size_t( ptr + index ) < total_size[0] );
		return ptr[index];
	}

	const R & operator [] ( size_t index ) const
	{
		assert( size_t( ptr + index ) < total_size[0] );
		return ptr[index];
	}
};


template< typename T, size_t N >        //Multi-array
class Marray
{
public:
	typedef T value_type;
	explicit Marray( unsigned src[] )
	{
		size_t total = 1;                   //total_size[M] M维数组的大小

		for( size_t i = N; i-- > 0; total *= src[i] ) total_size[N - 1 - i] = total;
		total_size[N] = total;
		ptr = new T[total];
		total_size[0] = size_t( ptr + total ); //total_size[0]用于边界判断
	}

	~Marray() { delete[] ptr; }

	size_t array_size( size_t m ) {  assert( m > 0 ); return total_size[m]; }

	Proxy< T, N - 1 > operator [] ( size_t index ) //or: return Proxy<T, N>(ptr, total_size)[index];
	{
		return Proxy< T, N - 1 >( ptr + total_size[N - 1] * index, total_size );
	}

	const Proxy< T, N - 1 > operator [] ( size_t index ) const
	{
		return Proxy< T, N - 1 >( ptr + total_size[N - 1] * index, total_size );
	}

	T *operator & () { return ptr; } //--
	const T *operator & () const { return ptr; }

private:
	T *ptr;
	size_t total_size[N + 1];
};

template< typename T > class Marray< T, 0 >{};
template< typename T > class Marray< T, 1 >{};

#define PR( x ) std::cout << # x << ": " << (x) << std::endl;
int main( int argc, char *argv[] )
{
	size_t sizes[] = { 2, 3 };
	Marray< int, 2 > a( sizes );

	a[0][1] = 10;
	PR( a[0][1] );
}
